Level 1

Varieties (ignoring reinforcement learning)

Supervised: classification

Supervised: regression

Unsupervised: data

Unsupervised: example result

Level 1: summary

Machine learning comes in two varieties:

• supervised learning:
  • typically lots of data-label pairs
  • aim is to build a model data -> label
  • categorical labels: classification
  • numeric labels: regression
• unsupervised learning:
  • unlabelled data
  • goals are vaguer but generally aims to simplify data and uncover patterns

Level 2

How does a computer “see” a cat?

How many images are possible?

• for a 20 x 20 binary image -> \(X\) has dimensionality of 400
• \(2^{400}\approx 2 \times 10^{120}\) possible images
• a very small proportion of those correspond to real world type images
• a very small proportion of real world images correspond to cats
• idea: even if dimensionality is big, effective dimensionality much lower
  • ML aims to find these lower dimensional representations

Supervised learning

Supervised learning

Rule determination

• Want to learn a rule \(f: X \rightarrow y\)
• Rule is a mathematical function controlled by low-dimensional parameters: \(f=f(\theta)\)
• Have training data:

\[(X_1, y_1), (X_2, y_2), ..., (X_n, y_n)\]

Can we learn \(f\) by optimising \(\theta\) on training data?

Example rules

What is \(\; f\)?

• Linear combination of elements of \(X\) (linear regression)
• Linear combination of functions of elements of \(X\) (kernel regression)
• Regression trees (random forests, boosted regression)
• Non-linear combinations of elements, stacked into multiple layers (deep learning)

How to learn optimal parameters?

Unsupervised learning

Unsupervised learning

Unsupervised learning: what does \(Z\) capture?

Unsupervised learning: clustering

Level 2: summary

• ML algorithms take numeric objects (vectors / matrices / tensors) as input
• intrinsic dimensionality of most things \(<\) raw dimensions: world simpler
• supervised learning:
  • determines a mathematical function to predict outputs from inputs
  • function depends on parameters which must be learned using training / testing data
  • learning based on optimising cost function

Level 2: summary

• unsupervised learning:
  • attempts to find more parsimonious representation of data
  • low dimensional variables learned may be more interpretable
  • clustering is an example of unsupervised ML

Questions?

Flavours of unsupervised learning

• dimensionality reduction
• clustering (really a type of dim. reduction)
• (outlier detection)

Dimensionality reduction

What is dimensionality reduction?

• most real life things have lots of features
• many features exhibit a degree of redundancy
• the effective number of important features is lower and we aim to identify these

Why reduce dimensions?

• universe is complex
• science aims to understand constituent laws to simplify universe
• more parsimonious theories have greater information compression and tend to generalise better

Why can dimensionality reduction help?

• improves interpretability
• aids visualisation
• extracts core features for supervised learning
• (lossy) information compression
• noise reduction

Classes of dimensionality reduction

• projection
• manifold learning

Wine data

Types

• Principal Components Analysis (PCA)
• Linear discriminant analysis
• Kernel PCA

PCA

Example raw data

Modelling data

• Looks normally distributed:

\[\begin{equation} (x_1,x_2)' \sim \mathcal{N}(\mu, \Sigma) \end{equation}\]

where \(\Sigma\) is dense.

• Can we use this assumption to move to more natural coordinate system? I.e.

\[\begin{equation} (y_1,y_2)' \sim \mathcal{N}(0, D) \end{equation}\]

where \(D\) is diagonal.

Example raw data

Assumed generative model

1st PC component axis

2nd PC component axis

How to obtain PC axes?

Remember, we’ve assumed:

\[\begin{equation} (x_1,x_2)' \sim \mathcal{N}(\mu, \Sigma) \end{equation}\]

1. Centre data:

\[\begin{equation} (\tilde x_{1,i}, \tilde x_{2,i}) = (x_{1,i}, x_{2,i}) - (\bar x_{1}, \bar x_{2}) \end{equation}\]

2. Estimate covariance matrix:

\[\begin{equation} \widehat{\Sigma} = \frac{1}{n}\sum (\tilde x_{1,i}, \tilde x_{2,i})' (\tilde x_{1,i}, \tilde x_{2,i}) \end{equation}\]

How to obtain PC axes?

3. Eigendecompose:

\[\begin{equation} \widehat{\Sigma} = P D P' \end{equation}\]

• \(P=[P_1, P_2]\) is matrix of eigenvectors of \(\widehat{\Sigma}\) representing PC directions:

\[\begin{align} y_1 &= P_1' . (\tilde x_1, \tilde x_2)\\ y_2 &= P_2' . (\tilde x_1, \tilde x_2) \end{align}\]

• \(D\) is diagonal with eigenvalues as diagonal elements
• eigenvector magnitudes indicate relative variance explained by that PC

Apply PCA to wine data

Pick price and points

Plot price and points

Apply PCA

What went wrong?

• PCA assumes data is distributed as multivariate normal
• price data very non-normal

Take log transform of price

Reapply PCA

Variance explained by each component

What do PCs mean?

Project data onto first two PCs

Sparse PCA

• PCA components typically load on all variables: tricky to assign meaning to them
• Sparse PCA methods penalise either the count or magnitude of non-zero loadings on the independent variables \(\implies\) can lead to more interpretable components

Plot sparse loadings

PCA: summary

• PCA is a projection method using linear transformations: collectively those linear transformations represent a rotation of coordinate axes
• PCA assumes data are multivariate normal
  • if not a good approximation, components can be poor representation
• works ok for simple data; less well for non-linear features

Questions?

What is it?

Essentially these methods try to learn the structure of the local manifolds in the data. (Also referred to as graph-based or embedding methods.)

• t-distributed stochastic nearest neighbour embedding (t-SNE)
• uniform manifold approximation and projection (UMAP)

High level detail

• original data in “data space” of dimensions \(\mathbb{R}^k\), where \(k\) is quite large
• t-SNE transforms data non-linearly to a “map space” of dimensions \(\mathbb{R}^2\) or \(\mathbb{R}^3\) typically
• constructs the mapping such that points close in “data space” are also close in “map space”

Mapping tries to preserves local neighbours

Similarity in data space: fuzzy neighbours

• imagine a Gaussian density around each point and define a conditional similarity:

\[\begin{equation} p_{j|i} = \frac{\exp(-|x_i-x_j|^2/2\sigma_i^2)}{\sum_{k\neq i} \exp(-|x_i-x_k|^2/2\sigma_i^2)} \end{equation}\]

where \(\sigma_i\) is different for each point: points in dense areas given smaller variance than those in sparse areas

• \(p_{j|i}\) measures the probability that \(x_i\) would pick \(x_j\) as its neighbour

Symmetrised similarity

Need a distance metric, so define:

\[\begin{equation} p_{ij} = \frac{1}{N} (p_{j|i} + p_{i|j}) \end{equation}\]

yielding a similarity matrix with elements \(p_{ij}\)

Similarity in map space

Uses Student-t distribution with one degree of freedom (the Cauchy):

\[\begin{equation} q_{ij} = \frac{1/(1+|z_i-z_j|^2)}{\sum_{k\neq i} 1/(1+|z_i-z_k|^2)} \end{equation}\]

How to choose \(z_i\)?

Algorithm to choose \(z_i\)

We can calculate the Kullback-Leibler divergence (not a distance!) from \(p_{ij}\rightarrow q_{ij}\):

\[\begin{equation} \text{KL} = \sum_{i,j} p_{ij} \log \frac{p_{ij}}{q_{ij}} \end{equation}\]

Minimise via gradient descent using \(\frac{\partial \text{KL}}{\partial z_i}\)

Picking \(\sigma_i\)

• more uncertainty (i.e. entropy) if \(\sigma_i\uparrow\)
• user specifies a “perplexity” hyperparameter which effectively determines number of nearest neighbours
• t-SNE chooses \(\sigma_i\) to meet this perplexity for each data point

Applying t-SNE to wine data

Perplexity=1

Perplexity: 100

What is UMAP?

embedding method like t-SNE, with similar steps:

• constructs a (fuzzy) nearest neighbour graph
• optimises a lower dimensional representation of this graph

Nearest neighbour graph construction: simplicial complexes

Low dimensional graph construction

Minimise cross-entropy assuming connection is described by Bernoulli dist:

\[\begin{equation} \sum_e w_h(e) \log \frac{w_h(e)}{w_l(e)} + (1 - w_h(e)) \log \frac{1-w_h(e)}{1-w_l(e)} \end{equation}\]

where \(w_h\) are high dimensional weights; \(w_l\) are low dimensional weights.

UMAP hyperparameters

• n_neighbours: the number of approximate nearest neighbours used to construct the high dimensional graph. Low values \(\implies\) local structure; high values \(\implies\) global structure but slower run time
• min_dist: minimum distance between points in low dimensional space. High values results in a more dense embedding

Applying UMAP to wine data

High min_dist

Low min_dist

Summary t-SNE and UMAP

• both manifold / emedding / graph methods
• t-SNE typically much slower
• global structure preserved better in UMAP
• hyperparameters really matter for both

Results from various dim reduction methods

Questions?

What does clustering aim to achieve?

K-means clustering

idea:

• set number of clusters, \(k\), a priori
• determine cluster centres such that distances of points within clusters to centres is minimised

K-means clustering

How to achieve k-means

1. randomly select \(k\) data points and make these the centres
2. determine distance of all points from each of the centres
3. assign clusters to nearest centres
4. calculate new centres as means of points within each cluster
5. repeat 2-4 until clusters stop changing (or max iterations reached)

Problem with k-means

Problem with k-means

Problem with k-means

• assumes data spherical (i.e. a multivariate Gaussian with diagonal covariance matrix)
• requires hard-coded number of clusters
• non-model based so hard to determine optimal number of clusters

Gaussian mixture models

Model-based clustering

data assumed to be generated by a mixture of Gaussians:

\[\begin{align} p(x_i) &= \sum_k p(x_i|z_i=k) p(z_i=k)\\ &= \sum_k \mathcal{N}(x_i|\mu_k, \Sigma_k) \pi_k \end{align}\]

where \(\mu_k\) and \(\Sigma_k\) are the mean and covariance matrix of the Gaussian mode corresponding to cluster \(k\); \(\pi_k\) is the mixture proportion

Generative model

1. roll a die with \(k\) faces with each face weighted by \(\pi_k\) \(\implies\) cluster \(j\)
2. draw \(x_i\sim\mathcal{N}(\mu_j, \Sigma_j)\)

repeat steps 1 and 2 repeatedly to draw a sample

How to fit

• since \(z_i\) are typically unobserved (this is the point of clustering), maximum likelihood estimation is hard
• instead expectation-maximisation (EM) algorithm is used

Revisiting star data

summary of GMMs

• better than k-means because model-based and more general Gaussian
• still requires number of clusters to be specified a priori, although model selection can take place to choose optimal cluster number
• do we actually believe there is fixed cluster number? Dirichlet process mixture models!

Summary

• unsupervised and supervised learning aim to achieve different goals
• dimensionality reduction is one variety of unsupervised learning
• PCA is a linear projection method
• t-SNE and UMAP are (non-linear) manifold learning methods that can better approximate lower dimensional approximations

Summary

• clustering methods can reduce data down to a single dimension
• k-means works for simple datasets
• GMMs are model-based and more general (but still have flaws)

Questions?